The present invention relates to a method for encoding a sequence of frames by means of a three-dimensional (3D) subband decomposition involving a spatial and temporal filtering step applied to the 3D spatio-temporal data which correspond to said sequence of frames considered as a 3D volume, said decomposition being applied to successive groups of frames only after the implementation, on said frames, of motion estimation and compensation operations in the low temporal subbands at each level of the temporal decomposition, the compensation operation leading, among the filtering pixels, to double-connected pixels corresponding to regions becoming uncovered during motion. The invention also relates to a method for decoding signals previously coded by means of such an encoding method.
Video compression schemes operate by removing redundant information from the signals before their transmission and then reconstructing, at the decoder side, an approximation of the image from the remaining compressed information. The temporal redundancy corresponds to the fact that pixel values are not independent but are correlated with their neighbours across successive frames. The reduction of this temporal redundancy is mainly achieved by two types of approaches: the xe2x80x9chybridxe2x80x9d or predictive approach, according to which a prediction of the current frame is computed based on the previously transmitted frames and only the prediction error, i.e. the difference between the current frame and its prediction, is intra-coded and transmitted, and the three-dimensional (3D, or 2D+t) approach in which the temporal redundancy is exploited by means of a temporal transform, in a similar way to the spatial techniques for removing the spatial redundancy (which corresponds to the fact that pixel values are not independent within the same frame).
In this 3D approach, the sequence of frames is processed as a 3D volume and thus the classical subband decomposition used in image coding can be extended to 3D spatio-temporal data by using separable transforms, for example wavelet or wavelet packets transforms implemented by means of filter banks. There is an anisotropy in such a 3D structure, but it can be taken into account by using different filter banks in the spatial and temporal directions (usually, Haar filters are used for temporal filtering since the added delay of using longer filters is undesirable ; furthermore, Haar filters are the only perfect reconstruction orthogonal filters which do not present the boundaries effect, since they are two-tap filters).
The coding efficiency of such a 3D coding scheme can be improved by performing motion estimation/compensation in the low temporal subbands at each level of the temporal decomposition. It was shown, for instance in xe2x80x9cThree-dimensional subband coding with motion compensationxe2x80x9d, by J. R. Ohm, IEEE Transactions on Image Processing, vol. 3, No5, September 1994, pp.559-571, that motion-compensated 3D subband coding leads to better visual and peak signal-to-noise ratio (PSNR) results than classical predictive schemes, for a given bitrate (in said document, a 3D subband decomposition with full motion compensation is performed using Haar filters in the temporal domain and a 2D discrete wavelet transformxe2x80x94or DWTxe2x80x94in the spatial domain).
However, the motion compensation raises the problem of points which are filtered twice or not filtered at all, as illustrated in FIG. 1. In the left part of FIG. 1, A and B respectively designate previous and current frames, and (a1 to a6), (b1 to b6) are pixels of said frames respectively (BBY=block boundary). The right part of FIG. 1 illustrates the process of motion compensation temporal filtering combined with block matching. As the connected pixels are filtered along the motion trajectory, and as matched blocks overlap with neighbouring blocks (except in case of no motion or translational motion), double-connected and unconnected pixels generally appear.
The strategy adopted in said document to cope with unconnected pixels is the following: for an unconnected pixel in the current frame (like b1), the original pixel value is inserted into the temporal low (L) subband. An unconnected pixel in the previous frame (like a3 and a4) is related to the same motion vector as its neighbours. The result of the high-pass filtering in the motion direction is put into the temporal high (H) subband at the unconnected pixel location (in the case of Haar filters, this represents the displaced frame difference). It is also proposed to perform the motion compensated prediction for the unconnected pixels in the previous frame by using the reconstructed frame just previous to it. Temporal subbands resulting from filtering replace the original frames: the temporal low (L) subband takes the place of the current frame, and the temporal high (H) subband replaces the reference frame.
Another method to cope with unconnected pixels is described in the document xe2x80x9cMotion-compensated 3-D subband coding of videoxe2x80x9d, by S. J. Choi and al, IEEE Transactions on Image Processing, vol. 8, no2, February 1999, pp.155-167, with reference to FIG. 2. For an unconnected pixel in the previous frame (like a3 and a4 ), the original value is inserted into the temporal low subband, which gives better visual results than the strategy defined in the first cited document. For an unconnected pixel in the current frame (like b1), a DFD (displaced frame difference) value is taken. By making the direction of motion estimation agree with that of motion compensation, the best available motion vector can be used for this DFD value, without the need of an additional motion estimation. The temporal subbands are relocated differently, as shown in the right part of FIG. 2: temporal low (L) subband replaces the reference frame, while temporal high (H) subband replaces the current frame. This is better suited in the case of unconnected pixels than the strategy of the first cited document, since the high-frequency subbands have smaller energy and are compatible with a DFD value for the unconnected pixels.
To sum up this approach, the following relations (1) to (3) are used:                                                                         H                [                                  m                  ,                  n                                            )                        =                                          1                                  2                                            ⁢                              (                                                      B                    ⁡                                          [                                              m                        ,                        n                                            ]                                                        -                                                            A                      ~                                        ⁡                                          [                                                                        m                          -                                                      d                            m                                                                          ,                                                  n                          -                                                      d                            n                                                                                              ]                                                                      )                                              ,                ⁢                  xe2x80x83                                    (        1        )                                                                                    L                ⁡                                  [                                                            m                      -                                                                        d                          _                                                m                                                              ,                                          n                      -                                                                        d                          _                                                n                                                                              ]                                            =                              xe2x80x83                            ⁢                                                1                                      2                                                  ⁢                                  xe2x80x83                                ⁢                                  (                                                                                    B                        ~                                            ⁡                                              [                                                  m                          -                                                                                    d                              _                                                        m                                                    +                                                      d                            m                                                                          ]                                                              +                                                                                                                                                                                                      xe2x80x83                                        ⁢                                                                  A                        ⁡                                                  [                                                                                    m                              -                                                                                                d                                  _                                                                m                                                                                      ,                                                          n                              -                                                                                                d                                  _                                                                n                                                                                                              ]                                                                    )                                                        ⁢                                      xe2x80x83                                    ⁢                  for                  ⁢                                      xe2x80x83                                    ⁢                  connecting                  ⁢                                      xe2x80x83                                    ⁢                  pixels                                ,                            ⁢                              xe2x80x83                                                                        (        2        )                                                      and            ⁢                                          xe2x80x83                            ⁢                              xe2x80x83                                      ⁢                          L              ⁡                              [                                  m                  ,                  n                                ]                                              =                                                    2                            ·                              A                ⁡                                  [                                      m                    ,                    n                                    ]                                                      ⁢                          xe2x80x83                        ⁢            for            ⁢                          xe2x80x83                        ⁢            unconnected            ⁢                          xe2x80x83                        ⁢            pixels                          ,                            (        3        )            
where (m,n) designates the position of the pixels, H[m,n], L[m,n] are temporal high- and low-subbands, A[m,n], B[m,n] are the previous and current frames, [dm, dn] is for a pixel the motion vector estimated between the two considered consecutive frames A and B, {overscore (d)}m, {overscore (d)}n are the nearest integers to dm, dn, and , {tilde over (B)} are interpolated values if motion pixels are subpixel accurate. In case of multiple connected pixels, A is calculated with the first pair (A, B) encountered.
In fact, the problem of unconnected and double connected pixels appears as closely related to that of covered/uncovered areas during motion. Indeed, when two objects having a common part in the frame at time T become separate at time T+1, two regions in the current frame will correspond, by motion compensation, to the same region in the reference frame: this is the uncovered area, that appears as double connected in the case of the previous analysis giving the relations (1) to (3). A possible situation is illustrated in FIG. 3, where FA designates a foreground area, belonging to a foreground object 1, and UR the uncovered area of a background object 2 when said regions become distinct (i.e. they do not overlap). The approach described in the second document associates to these pixels the first block encountered in the motion estimation process.
It is the object of the invention to propose an optimized solution with respect to the previously described approach.
To this end, the invention relates to an encoding method such as defined in the introductive part of the description and which is moreover characterized in that it comprises the following steps:
(1) a motion compensated temporal filtering step between a previous reference frame A and a current frame B, said step itself comprising in a first time a computation sub-step of the high frequency subband, followed by a computation sub-step of the low frequency subband, using only the reference frame A and the previously computed high frequency subband, said computations being carried out according to the following relations:
H[m,n]=(B[m,n]xe2x88x92Ã[mxe2x88x92dm,nxe2x88x92dn])/{square root over (2)},
L[mxe2x88x92{overscore (d)}m,nxe2x88x92{overscore (d)}n]={tilde over (H)}[mxe2x88x92{overscore (d)}m+dm,nxe2x88x92{overscore (d)}n+dn]+{square root over (2)}A[mxe2x88x92{overscore (d)}m,nxe2x88x92{overscore (d)}n] for connected pixels,
L [m, n]={square root over (2+L )}.A[m,n] for unconnected pixels,xe2x80x83xe2x80x83(c)
where (m,n) designates the position of the pixels, H[m,n], L[m,n] are temporal high- and low-subbands, A[m,n], B[m,n] are the consecutive previous and current frames, [dm, dn] is for a pixel the motion vector estimated between the frames A and B, {overscore (d)}m, {overscore (d)}n are the nearest integers to dm, dn, and, Ã, {tilde over (H)} are interpolated values;
(2) an identification step of said uncovered regions as being related to double-connected pixels, those pixels leading to a minimum energy in the detail subband;
(3) a decision step, provided for choosing in the current frame, for the temporal filtering of a double-connected pixel of the reference frame, the corresponding pixel that leads to a minimum energy of the detail subband..
If two objects 1 and 2 are superposed in the reference frame (left part of FIG. 3), there is an occluded area in one of them and only the foreground area FA belonging to the other is available. If these objects become separated (right part of FIG. 3) in the current frame, the motion estimation algorithm will identify two regions in the current frame for compensation. As the real motion corresponds to the foreground area in object 1, the uncovered area UA in object 2 will give rise to a higher energy of the detail subband, which represents the difference between the compensated reference frame and the current frame. Indeed, if the real motion corresponds to the object 1, this difference will be very small in the case of the foreground area and high for the uncovered area in object 2. According to the invention, this observation is used to choose the correct pixel for the temporal filtering process.
The invention also relates to a method for decoding digital signals previously coded by such a method, said decoding method being characterized in that the reconstruction of the pixels of the reference and current frames A and B is obtained by means of computation steps based on the values of the corresponding pixels in the low and high frequency subbands, said computations being made according to the following relations:                                           A            ⁡                          [                                                m                  -                                                            d                      _                                        m                                                  ,                                  n                  -                                                            d                      _                                        n                                                              ]                                =                                    1                              2                                      ⁢                          xe2x80x83                        ⁢                          (                                                L                  ⁡                                      [                                                                  m                        -                                                                              d                            _                                                    m                                                                    ,                                              n                        -                                                                              d                            _                                                    n                                                                                      ]                                                  -                                                      H                    ~                                    ⁡                                      [                                                                  m                        -                                                                              d                            _                                                    m                                                +                                                  d                          m                                                                    ,                                              n                        -                                                                              d                            _                                                    n                                                +                                                  d                          n                                                                                      ]                                                              )                                      ⁢                  
                ⁢                  (                      for            ⁢                          xe2x80x83                        ⁢            connected            ⁢                          xe2x80x83                        ⁢            pixels                    )                ⁢                  "IndentingNewLine"                ⁢                              A            ⁡                          [                              m                ,                n                            ]                                =                                                    1                                  2                                            ·                              L                ⁡                                  [                                      m                    ,                    n                                    ]                                                      ⁢                          xe2x80x83                        ⁢                          (                              for                ⁢                                  xe2x80x83                                ⁢                unconnected                ⁢                                  xe2x80x83                                ⁢                pixels                            )                                                          xe2x80x83                                          B          ⁡                      [                          m              ,              n                        ]                          =                                            2                        ⁢                          H              ⁡                              [                                  m                  ,                  n                                ]                                              +                                                    A                ~                            ⁡                              [                                                      m                    -                                          d                      m                                                        ,                                      n                    -                                          d                      n                                                                      ]                                      .                                              (        c        )            